package com.javabase.y2022.m05.day0517.v4;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/17 上午 10:31
 * @version: 1.0
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 2, 1, 5, 6, 3, 2, 1};
//        System.out.println(new Solution().mergeSorted(arr));
        System.out.println(new Solution().mergeSorted2(arr));

        for (int i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
    }

    public int mergeSorted(int[] arr) {
        int L = 0;
        int R = arr.length - 1;
        return process(arr, L, R);
    }

    public static int process(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        int ans =
                process(arr, L, M) +
                        process(arr, M + 1, R) +
                        merge(arr, L, M, R);
        return ans;
    }

    public static int merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = help.length - 1;
        int p1 = M, p2 = R;
        int ans = 0;
        while (p1 >= L && p2 >= M + 1) {
            ans += arr[p1] > arr[p2] ? (p2 - M) : 0;
            help[i--] = arr[p1] < arr[p2] ? arr[p1--] : arr[p2--];
        }
        while (p1 >= L) {
            help[i--] = arr[p1--];
        }
        while (p2 >= M + 1) {
            help[i--] = arr[p2--];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
        return ans;
    }

    public static int mergeSorted2(int[] arr) {
        int L = 0;
        int R = arr.length - 1;
        return process2(arr, L, R);
    }

    public static int process2(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return process2(arr, 0, M) +
                process2(arr, M + 1, R) +
                merge2(arr, L, M, R);
    }

    public static int merge2(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int p1 = L, p2 = M + 1;
        int i = 0;
        int ans = 0;
        while (p1 <= M && p2 <= R) {
            if (arr[p2] < arr[p1]) {
                ans += p2 - M;
            }
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
        return ans;
    }
}
